#include "stdafx.h"
#include "tango frenzy.h"

extern int numar_noduri;
extern nod* headref;
nod * headtango=NULL;
lista *first=NULL;

int v[32];
int nr=1;


nod * cautareparinte(nod * rad,int info,bool *ok)
{
	nod *prv,*crt=rad;
	if (crt==NULL) return NULL;
	while (crt!=NULL)
	{
		if (info<crt->info) {
			prv=crt;
			crt=crt->left;
		}
		else
		{
			prv=crt;
			crt=crt->right;
		}
	}
	(*ok)=0;
	if (prv->info<info) (*ok)=1;
	return prv;
}

void createtango(lista *elem)
{
	int info=0;
	bool *ok=(bool*)malloc(sizeof(bool));;
	nod *headaux=NULL,*parent=NULL;
	if (!elem) return;
	headaux=elem->radacina;
	info=headaux->info;
	parent=cautareparinte(headtango,info,ok);
	if (!parent) headtango=copyarbore(headaux);
	else
		{
			if ((*ok)==false) 
				parent->left=copyarbore(headaux);
			else 
				parent->right=copyarbore(headaux);
	}
	free(ok);
	createtango(elem->next);
}
	

	


nod * crearearbaux(int left, int right)
{
	int dif;
	nod *crt=NULL;
	if(right-left<=1) return NULL;
	crt=(nod*)malloc(sizeof(nod));
	dif=right-left;
	dif=dif/2;
	crt->isroot=0;
	crt->info=v[left+dif];
	if (right==nr&&left==0) crt->isroot=1;
	crt->left=crearearbaux(left,left+dif);
	crt->right=crearearbaux(left+dif,right);
	return crt;
}


nod * crearearbore()
{
	nod *crt;
	int i,j,aux;
	if (nr==1) return NULL;
	for (i=1;i<nr-1;i++)
		for (j=i+1;j<nr;j++)
			if (v[i]>v[j])
			{
				aux=v[i];
				v[i]=v[j];
				v[j]=aux;
			}
	crt=crearearbaux(0,nr);
	return crt;
}

void adaugarelista()
{
	nod * crt=NULL;
	lista *element=NULL,*o,*p;
	crt=crearearbore();
	if (!crt) return;
	element=(lista*)malloc(sizeof(lista));
	element->nrelem=nr-1;
	element->radacina=crt;
	element->next=NULL;
	o=first;
	p=o;
	while (o!=NULL)
		if (o->nrelem>=element->nrelem)
		{
			p=o;
			o=o->next;
		}
		else o=NULL;
	if (p==NULL)
		first=element;
	else
	{
		element->next=p->next;
		p->next=element;
	};
}

void parcurgereref(nod * root)
{
	if (root==NULL) return;
	v[nr]=root->info;
	nr++;
	parcurgereref(root->left);
	adaugarelista();
	nr=1;
	parcurgereref(root->right);
	adaugarelista();
}


void crearetango()
{
	parcurgereref(headref);
	createtango(first);
	if (1);
}

void tangotree()
{
	freememnod(headtango);
	headtango=NULL;
	freelista(first);
	first=NULL;
	crearetango();		
	//tangosearch(13);		//face cautarea retine valorile in vechihead,vechifirst,etc
	//freetangotree();		//inlocuieste first,headref,headtango cu cele gasite la tangosearch, si elibereaza memoria acestora
}